package com.example.algorithm.greedy;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个字符串 s ，s只包含26个小写字母，请你去除字符串中重复的字母，使得每个字母只出现一次。
 * 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 * <p>
 * 示例 1：
 * 输入：s = "bcabc"
 * 输出："abc"
 * <p>
 * 示例 2：
 * 输入：s = "cbacdcbc"
 * 输出："acdb"
 */
public class Leetcode316_RemoveDuplicateLetters {

    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters2("cbcadcbc"));

    }


    /**
     * 解法二:使用栈进行优化
     * 栈 + 贪心
     * <p>
     * 使用栈存放当前扫描过字符串的处理结果
     * 若当前字符小于栈顶字符且栈顶字符在之后还会出现，那么使用当前字符替换栈顶字符一定可以得到字典序更小的结果
     * <p>
     * 首先浏览一遍字符串，确定每个字符在串中最后一次出现的位置
     * 再浏览一遍字符串，对当前字符：
     * • 若栈为空，压栈
     * • 若栈不空，且当前字符在栈中出现过，跳过当前字符
     * • 否则比较当前字符与栈顶字符
     *   • 若当前字符大于栈顶字符，压栈
     *   • 若栈顶字符大于当前字符且最后出现位置在当前位置之后，栈顶出栈，继续比较当前字
     *        符与新栈顶字符，直至栈为空或栈顶字符小于当前字符或栈顶字符未在当前位置后出现
     *        过，将当前字符压栈
     *
     * @param s
     * @return
     */
    public static String removeDuplicateLetters2(String s) {
        if (s == null || s.length() <= 1)
            return s;

        int[] lastOccurrence = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence[s.charAt(i) - 'a'] = i;
        }

        Deque<Character> stack = new LinkedList<>();
        boolean[] charIsInStack = new boolean[26];// 用于记录字母是否已经存在于栈中

        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (!charIsInStack[cur - 'a']) { // 当前索引对应的字母不存在于栈中
                // 栈为空、或当前字符大于栈顶字符、或栈顶字符在当前字符后不再出现，当前字符压栈
                while (!stack.isEmpty() && cur < stack.peek()
                        && lastOccurrence[stack.peek() - 'a'] > i) {
                    charIsInStack[stack.pop() - 'a'] = false;
                }

                stack.push(cur);
                charIsInStack[cur - 'a'] = true;

            }
        }

        // 将栈中的字⺟母连接起来
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.reverse().toString();
    }

    /**
     * 解法一:贪心算法
     * <p>
     * 思路:
     * 每次都选择尽可能的小字符作为本轮的首字符，
     * 同时要保证本轮选择的首字符前的其他字符在首字符后出现过
     *
     * @param s
     * @return
     */
    public static String removeDuplicateLetters1(String s) {
        // 递归结束条件
        if (s.length() <= 1)
            return s;

        //主功能：1. 记录每个字母最后出现位置
        // 因为字符只有26个小写字母，所以可以根据字母相对于'a'的偏移来存储字母最后出现的索引位置
        int[] lastOccurrence = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence[s.charAt(i) - 'a'] = i;
        }

        // 2.尝试找到尽可能小的首字符
        int pos = 0;// 用于记录当前处理理过的字符串中最⼩的字符位置
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) {
                pos = i;
            }

            // 说明这个字母是最后一次出现在字符串中，本轮的开头最小字符就确定了，因此要退出循环
            if (lastOccurrence[s.charAt(i) - 'a'] == i)
                break;
        }

        // 3.在剩余⼦子串串中删掉首字符
        System.out.println(pos + "    " + s.substring(pos + 1));
        String subStr = s.substring(pos + 1).replace("" + s.charAt(pos), "");
        System.out.println(subStr);
        System.out.println("================");
        // 递归寻找下⼀个首字符
        // 关系式：f(n)=x+f(m) x:本轮找到的最⼩首字符，m:剩余子串中剔除首字符得到的子串
        return s.charAt(pos) + removeDuplicateLetters1(subStr);
    }
}
